package leetcode.problems;

import org.junit.Test;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * Created by gmwang on 2020/1/31
 * Relative Sort Array
 * 相对排序数组
 */
public class RelativeSortArray {
    /**
     * Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.
     * 给定两个数组arr1 arr2, arr2的元素是不同的,所有arr2的元素在arr1都存在。
     * Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2.
     * 排序的元素arr1这样项目的相对顺序arr1 arr2是一样的。
     * Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.
     * 元素不应该出现在arr2 arr1年底按升序。
     *
     *
     * Example 1:
     *
     * Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
     * Output: [2,2,2,1,4,3,3,9,6,7,19]
     *
     *
     * Constraints:
     *
     * arr1.length, arr2.length <= 1000
     * 0 <= arr1[i], arr2[i] <= 1000
     * Each arr2[i] is distinct.
     * Each arr2[i] is in arr1.
     **/
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int [] result = new int[arr1.length];
        int breaking = 0;
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < arr2.length; i++) {
            int tiny = arr2[i];
            for (int j = 0; j < arr1.length; j++) {
                if(tiny == arr1[j]){
                    result[breaking ++]=tiny;
                    arr1[j] = -1;
                }
            }
        }
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != -1){
                linkedList.push(arr1[i]);
            }
        }
        Collections.sort(linkedList);
        while(!linkedList.isEmpty()){
            result[breaking++] = linkedList.pop();
        }
        return result;
    }
    @Test
    public void test() {
        int [] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int [] arr2 = {2,1,4,3,9,6};
        int [] res = relativeSortArray(arr1,arr2);
        System.out.println(Arrays.toString(res));
    }
}
